package com.learn.algorithm;

import java.util.Arrays;

public class Sort {

    /**
     * 交换数组中第i个位置和第j个位置上的元素
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 选择排序
     * 算法思路:
     * 1. 0~N-1中选最小的放到0位置
     * 2. 1~N-1中选最小的放到1位置
     * 3. 2~N-1中选最小的放到2位置
     * ...
     */
    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[min]) {
                    min = j;
                }
            }
            swap(array, i, min);
        }
    }

    /**
     * 冒泡排序
     * 1. 0~N-1上的元素两两比较, 将大的放在右边, 小的放在左边
     * 2. 0~N-2上的元素两两比较, 将大的放在右边, 小的放在左边
     * 3. 0~N-3上的元素两两比较, 将大的放在右边, 小的放在左边
     * ...
     */
    public static void bubbleSort(int[] array) {
        int N = array.length;
        for (int end = N - 1; end >= 0; end--) {
            for (int second = 1; second <= end; second++) {
                if (array[second] < array[second - 1]) {
                    swap(array, second, second - 1);
                }
            }
        }
    }

    /**
     * 插入排序
     * 1. 0~0范围上有序 自动完成
     * 2. 0~1范围上有序
     * 3. 0~2范围上有序
     * ...
     */
    public static void insertionSort1(int[] array) {
        int N = array.length;
        for (int end = 1; end < N; end++) {
//            for (int j = end; j > 0; j--) {
//                if (array[j] < array[j - 1]) {
//                    swap(array, j, j - 1);
//                }
//            }
            int newNumIndex = end;
            while (newNumIndex - 1 >= 0 && array[newNumIndex - 1] > array[newNumIndex]) {
                swap(array, newNumIndex - 1, newNumIndex);
                newNumIndex--;
            }
        }
    }

    public static void insertionSort2(int[] array) {
        int N = array.length;
        for (int end = 1; end < N; end++) {
            for (int j = end; j > 0 && (array[j] < array[j - 1]); j--) {
                swap(array, j, j - 1);
            }
        }
    }

    public static int BASE = 10;
    public static int MAX = 50001;
    public static int[] help = new int[MAX];
    public static int[] cnts = new int[BASE];

    public static int[] sortArray(int[] array) {
        int N = array.length;
        if (N > 1) {
            int min = array[0];
            for (int i = 1; i < N; i++) {
                min = Math.min(min, array[i]);
            }
            int max = 0;
            for (int i = 0; i < N; i++) {
                array[i] -= min;
                max = Math.max(max, array[i]);
            }
            radixSort(array, N, bits(max));
            for (int i = 0; i < N; i++) {
                array[i] += min;
            }
        }
        return array;
    }

    /**
     * @param array 待排序数组 需要保证里面都是非负数
     * @param n     arr数组的长度
     * @param bits  arr数组中的最大值在BASE进制下的位数
     */
    public static void radixSort(int[] array, int n, int bits) {
        for (int offset = 1; bits > 0; offset *= BASE, bits--) {
            // 桶清0
            Arrays.fill(cnts, 0);
            for (int i = 0; i < n; i++) {
                // 提取arr[i]中 个位、十位、百位...等数位上的数字 并统计其出现的次数
                cnts[(array[i] / offset) % BASE]++;
            }

            // 计算前缀和
            for (int i = 1; i < BASE; i++) {
                cnts[i] = cnts[i] + cnts[i - 1];
            }

            for (int i = n - 1; i >= 0; i--) {
                // 前缀数量分区的技巧
                // 数字提取某一位的技巧
                help[--cnts[(array[i] / offset) % BASE]] = array[i];
            }
            System.arraycopy(help, 0, array, 0, n);
        }
    }

    public static int bits(int max) {
        int result = 0;
        while (max > 0) {
            result++;
            max /= BASE;
        }
        return result;
    }

    private static void mergeSort(int[] array, int low, int high) {
        if (low == high) return;
        int mid = low + ((high - low) >> 1);
        mergeSort(array, low, mid);
        mergeSort(array, mid + 1, high);
        merge(array, low, mid, high);
    }

    private static void merge(int[] array, int low, int mid, int high) {
        int i = low;
        int k = low;
        int j = mid + 1;
        while (i <= mid && j <= high) {
            help[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        }
        while (i <= mid) {
            help[k++] = array[i++];
        }
        while (j <= high) {
            help[k++] = array[j++];
        }

        for (k = low; k <= high; k++) {
            array[k] = help[k];
        }
    }

    public static void print(int[] array) {
        for (int e : array) {
            System.out.print(e + " ");
        }
        System.out.println();
    }

    public static void quickSort1(int[] array, int l, int r) {
        if (l >= r) {
            return;
        }

        int x = array[l + (int) ((r - l + 1) * Math.random())];
        int mid = partition1(array, l, r, x);
        quickSort1(array, l, mid - 1);
        quickSort1(array, mid + 1, r);
    }

    // array[]在l...r范围上存在x, 把小于等于x的放在array的左边, 大于x的放在array的右边
    // 确保划分完成后小于等于x的最右边的数字是x
    public static int partition1(int[] array, int l, int r, int x) {
        // 1. i a = l, array[i] <= x则 i a交换 i++ a++
        // 2. array[i] > x 则i++ 次数小于x的边界不能扩大
        int a = l; // 表示小于等于x的位置的边界
        int xi = 0; // 记录<=x的范围内的任意个x 跟最终 a-1位置交换
        for (int i = l; i <= r; i++) {
            if (array[i] <= x) {
                swap(array, a, i);
                if (array[a] == x) {
                    xi = a;
                }
                a++;
            }
        }
        swap(array, xi, a - 1);
        return a - 1;
    }

    public static void quickSort2(int[] array, int l, int r) {
        if (l >= r) {
            return;
        }

        int x = array[l + (int) ((r - l + 1) * Math.random())];
        int[] mid = partition2(array, l, r, x);
        quickSort1(array, l, mid[0]);
        quickSort1(array, mid[1], r);
    }

    public static int[] partition2(int[] array, int l, int r, int x) {
        int a = l;
        int b = r;
        for (int i = l; i <= r; i++) {
            if (array[i] < x) {
                swap(array, a, i);
                a++;
            } else if (array[i] > x) {
                swap(array, b, i);
                b--;
            } else {
                a++;
            }
        }
        return new int[]{a - 1, b + 1};
    }

    public static void heapInsert(int[] array, int i) {
        while (array[i] > array[(i - 1) / 2]) {
            swap(array, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    public static void heayify(int[] array, int i, int size) {
        int l = 2 * i + 1;
        while (l < size) {
            // 左孩子 l 右孩子 l + 1 找到左右孩子中最大的那个
            // 存在右孩子, 并且右孩子的值比左孩子大 那么就选右孩子, 否则选左孩子
            int best = l + 1 < size && array[l + 1] > array[l] ? l + 1 : l;
            // 找到最大的孩子跟父亲相比, 哪个最大, 记录其位置
            best = array[best] > array[i] ? best : i;
            // 父节点比最大的孩子还大 可以不用交换了
            if (best == i) {
                break;
            }
            swap(array, i, best);
            i = best;
            l = 2 * i + 1;
        }
    }

    public static void heapSort1(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i++) {
            heapInsert(array, i);
        }
        int size = n;
        while (size > 1) {
            // 把堆顶元素跟数组最后一个元素置换
            swap(array, 0, --size);
            // 调整堆
            heayify(array, 0, size);
        }
    }

    public static void heapSort2(int[] array) {
        int n = array.length;
        for (int i = n - 1; i >= 0; i--) {
            heayify(array, i, n);
        }
        int size = n;
        while (size > 1) {
            // 把堆顶元素跟数组最后一个元素置换
            swap(array, 0, --size);
            // 调整堆
            heayify(array, 0, size);
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{-74, 48, -20, 2, 10, -84, -5, -9, 11, -24, -91, 2, -71, 64, 63, 80, 28, -30, -58, -11, -44, -87, -22, 54, -74, -10, -55, -28, -46, 29, 10, 50, -72, 34, 26, 25, 8, 51, 13, 30, 35, -8, 50, 65, -6, 16, -2, 21, -78, 35, -13, 14, 23, -3, 26, -90, 86, 25, -56, 91, -13, 92, -25, 37, 57, -20, -69, 98, 95, 45, 47, 29, 86, -28, 73, -44, -46, 65, -84, -96, -24, -12, 72, -68, 93, 57, 92, 52, -45, -2, 85, -63, 56, 55, 12, -85, 77, -39};
//        selectionSort(array);
//        bubbleSort(array);
//        insertionSort1(array);
//        insertionSort2(array);
//        sortArray(array);
//        mergeSort(array, 0, array.length - 1);
//        quickSort2(array, 0, array.length - 1);
        heapSort1(array);
        heapSort2(array);
        print(array);
    }
}
